P3195 [HNOI2008]玩具装箱TOY

这道题像我这样的 dpdp 蒟蒻都能一眼看出 dpdp 式:

sumsumcc 的前缀和,则有

dp[i]=min{dp[j]+((ij1)+(sum[i]sum[j])L)2}  (0j<i)dp[i]=min\{ dp[j]+((i-j-1)+(sum[i]-sum[j])-L)^2 \} ~~ (0 \le j < i)

阅读全文 »

CF487B Strip

一道并不难的 dpdp 题。转移式很好列:

dp[i]=min{dp[j]+1}    (0jil &&max(j+1,i)min(j+1,i)<=s)dp[i]=min\{ dp[j]+1 \} ~~~~ (0 \le j \le i - l~\&\&max(j+1,i)-min(j+1,i)<=s)

阅读全文 »

P3503 [POI2010]KLO-Blocks

首先可以知道一个区间满足条件的必要条件是该区间的平均数大于等于 kk

进一步可以发现这是一个充要条件。因为大于 kk 的数一定能填补到小于 kk 的数。

记一个合法的区间为 [l,r][l,r]sumsumaa 的前缀和。

阅读全文 »

P5496 【模板】回文自动机(PAM)

不懂回文自动机的可以看这篇博客

现在默认大家都懂,用 Cnt[i]Cnt[i] 表示以 ii 结尾的回文串的个数。

由于 Link[i]Link[i] 表示 ii 的最长回文后缀,所以 Cnt[i]=Cnt[Link[i]]+1Cnt[i]=Cnt[Link[i]]+1(加上 ii 点所标示的一个回文串)

阅读全文 »

P3649 [APIO2014]回文串

不懂回文自动机的点这里

如果单纯的记录每个点结束回文串的数量,因为我们用的增量法 ,wwww 只会被计算一次 , 第二个样例都过不了。

所以在构建回文自动机后 , 我们将每一个 Cnt[Link[u]]+=Link[u]Cnt[Link[u]]+=Link[u] , 就可以避免由上述方法带来的影响了。

阅读全文 »

P4555 [国家集训队]最长双回文串

显然是一道回文自动机板题。

L[i]L[i] 表示以 ii 号点为左端点的最长回文串 , R[i]R[i] 表示以 ii 号点为右端点的最长回文串。

L[i]L[i] 可以通过将回文串倒过来建自动机求得 , R[i]R[i] 可以直接用原回文串建自动机求得。

阅读全文 »

CF17E Palisection

答案为所有的回文串组合-不相交的回文串组合。

cntcnt 为回文串个数 , 可以通过计算每个节点的回文串数量求得。

不相交的回文组合也比较好求,先算出以 ii 为左端点和右端点的回文串数量 L[i]L[i] , R[i]R[i]

阅读全文 »